import java.util.*;

/**
 * Created by xiebang
 * Description
 * User:小谢
 * Date:2021-09-28
 * Time:19:25
 */
class Node{
    public char val;
    public Node right;
    public Node left;

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }

    public Node(char val) {
        this.val = val;
    }
}
public class TestBinaryTree {
    public Node createTree(){
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
        Node H = new Node('H');


        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    void preOrderTraversal(Node root){
        if(root == null){
            return;
        }
        System.out.print(root.val + "->");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    void inOrderTraversal(Node root){
        if(root == null){
            return;
        }

        inOrderTraversal(root.left);
        System.out.print(root.val + "->");
        inOrderTraversal(root.right);
    }

    void postOrderTraversal(Node root){
        if(root == null){
            return;
        }

        postOrderTraversal(root.left);

        postOrderTraversal(root.right);
        System.out.print(root.val + "->");
    }

    static int size = 0;
    void getSize11(Node root){
        if (root == null){
            return;
        }
        this.size++;
        getSize11(root.left);
        getSize11(root.right);
    }
    int getSize2(Node root){
    int sz = 0;
    if (root == null){
        return 0;
    }
//    sz++;
//    int leftszie = getSize2(root.left);
//    sz += leftszie;
//    int rightsize = getSize2(root.right);
//    sz += rightsize;
//    return sz;
        return getSize2(root.right) + getSize2(root.left) + 1;
    }

    //遍历思想来求叶子节点
    static int leafSize = 0;
    void getLeafSize1(Node root){
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null){
            leafSize++;
            return;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

    int getLeafSize2(Node root){

        if (root == null){
            return 0;
        }
        if (root.left == null && root.right==null){
            return 1;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right);
    }

    //第k层的节点个数
    int getKleveSize(Node root,int k) {
        if (root == null){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKleveSize(root.left,k-1) + getKleveSize(root.right,k-1);
    }

    //当前二叉树的高度
    int  getHeight(Node root){
        if (root == null){
            return 0;
        }

        int leftHeight = getHeight(root.left) ;
        int rightHeight = getHeight(root.right) ;
        return (leftHeight > rightHeight)? leftHeight+1:rightHeight+1;
    }

    Node find(Node root, char val){
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        Node ret = find(root.left,val);
        if (ret!= null){
            return ret;
        }
        ret  = find(root.right,val);
        if (ret!= null){
            return ret;
        }
        return null;
    }

    //非递归的中序遍历
    void noInOrderTraversal(Node root){
        Stack<Node> stack = new Stack<>();
        Node cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            Node top = stack.pop();
            System.out.print(top.val + "->");
            cur = top.right;
        }
//        Node curNode = root;
//        while (!stack.empty() || curNode!=null) {
//            while (curNode != null) {
//                stack.push(curNode);
//                curNode = curNode.left;
//            }
//            //到了最左边，这个时候就要出栈
//            if (!stack.empty()) {
//                Node tmp = stack.peek();
//                stack.pop();
//                System.out.print(tmp.val + "->");
//                curNode = tmp.right;
//            }
//        }

    }

    //非递归的前序遍历
    void nopreOrderTraversal(Node root){
        Stack<Node> stack = new Stack<>();
        Node curNode = root;

        while (curNode != null || !stack.empty()) {
            while (curNode != null) {
                System.out.print(curNode.val + "->");
                stack.push(curNode);
                curNode = curNode.left;
            }
            Node top = stack.pop();
            curNode = top.right;
        }

//        Node curNode = root;
//        while (curNode != null || !stack.empty()){
//            while (curNode != null) {
//                System.out.print(curNode.val + "->");
//
//                if (curNode.left != null || curNode.right != null) {
//                    stack.push(curNode);
//                }
//
//                curNode = curNode.left;
//            }
//
//            if (!stack.empty()){
//                Node tmp = stack.peek();
//                stack.pop();
//                curNode = tmp.right;
//            }
//        }


    }


    void nopostOrderTraversal(Node root){
        Stack<Node> stack = new Stack<>();
        Node curNode = root;
        while (curNode != null || !stack.empty()){
            while (curNode != null){
                stack.push(curNode);
                curNode = curNode.left;
            }

            Node tmp = null;
            if (!stack.empty()){
                tmp = stack.peek();
                stack.pop();
                curNode = tmp;
            }


        }
    }

    void levelOrderTraversal(Node root){
        if (root == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node top = queue.poll();
            System.out.print(top.val + "->");
            if (top.left!= null){
                queue.offer(top.left);
            }

            if (top.right != null){
                queue.offer(top.right);
            }
        }

    }
    boolean isCompleteTree(Node root){
        if (root == null) return false;

        Queue<Node> queue = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            Node top = queue.peek();
            if (top == null) {
                break;
            }
            queue.offer(top.left);
            queue.offer(top.right);

        }

        while (!queue.isEmpty()){
            Node tmp = queue.peek();
            if (tmp != null){
                return false;
            }
            queue.poll();
        }
        return true;
    }




    //非递归后续遍历
    void postOrderTraversalNor(Node root){
        if (root == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        Node rightChild = null;
        Node cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();

            if (cur.right == null || cur.right == rightChild){//或者cur,right 已经被打印了{
                stack.pop();
                System.out.print(cur.val + "->");
                rightChild = cur;
                cur = null;//不置空一直打印第一个 这个Y打印了不能再入栈
            }else {
                cur = cur.right;
            }

        }
    }
}
